package leetcode;

/**
 * 分隔链表
 */
public class Solution86 {

    public ListNode partition(ListNode head, int x) {
        ListNode maxThan = new ListNode(-1);
        ListNode maxThanTemp = maxThan;
        ListNode lessThan = new ListNode(-1);
        ListNode lessThanTemp = lessThan;
        ListNode temp = head;
        while(temp!=null){
            if(temp.val >=x){
                maxThanTemp.next = temp;
                maxThanTemp = maxThanTemp.next;
            }else{
                lessThanTemp.next = temp;
                lessThanTemp = lessThanTemp.next;
            }
            temp = temp.next;
        }
        maxThanTemp.next = null;
        lessThanTemp.next = maxThan.next;
        return lessThan.next;

    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }